package pack0720;

import org.w3c.dom.*;

public class Tree {

    public Node root;   //根节点

    public int length;  //树的节点数

    //存储数据
    public void add(int n) {
        length++;
        //第一次调用存储数据,放到根节点中
        if (root == null) {           //没有根节点
            root = new Node(n);
        } else {                     //有根节点,树已经有了
            Node node = new Node(n);
            //定义一个引用指向根节点
            Node pre = root;
            //定义一个父引用指向根节点
            Node parent = pre;

            //遍历
            while (true) {
                if (pre.n > n) {         //if判断走左边还是走右边(不管在哪比大小,都在这里)
                    //向左走
                    parent = pre;          //pre是根节点,将值赋给parent
                    pre = pre.left;        //则第二个数有了可以参考的节点来定位自己的位置    根节点大于第二个数,则走左边,所以是left
                    if (pre == null) {     //如果左边的数为空
                        parent.left = node;   //将值附进去
                        break;                  //结束
                    }
                } else {
                    //向右走
                    parent = pre;
                    pre = pre.right;
                    if (pre == null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }
    }

    //前序遍历,先打印根数据,再打印左树数据,再右树数据
    //中序遍历,先打印左数据,再打印根数据,再右数据
    //后序遍历,先打印左数据,再打印右数据,再根数据

    //中序遍历
    public void centerOrder(Node root){
        if(root==null){     //树上无数据
            return;      //返回上一级
        }else{
            centerOrder(root.left);   //遍历左子树
            System.out.println(root.n);  //打印当前根节点
            centerOrder(root.right);   //遍历右子树
        }
    }

    public int size() {
        return length;
    }

    public class Node {

        public int n;

        public Node left;   //左节点

        public Node right;   //右节点

        public Node(int n) {
            this.n = n;
        }
    }
}